/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 单向环链表;

/**
 * @Description 约瑟夫问题
 * 设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，
 * 数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，
 * 直到所有人出列为止，由此产生一个出队编号的序列。
 * <p>
 * 提示：用一个不带头结点的循环链表来处理Josephu问题：
 * 先构成一个有n个结点的单循环链表
 * ，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，
 * 然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
 * @Author 俊昭
 * @Date 2022/4/28
 */
public class JosephuQue {
    private static final Node head = new Node(0);
    private static final Node tail = new Node(0);


    public static void addNode(int n) {
        if (n < 1) {
            throw new RuntimeException("不可以小于一!");
        } else {
            tail.next = head;
            Node temp = new Node(1);
            head.next = temp;
            for (int i = 0; i < n; i++) {
                if (i == n - 1) {
                    temp.next = tail;
                } else {
                    temp.next = new Node(i + 2);
                    temp = temp.next;
                }
            }
        }
    }

    /**
     * @param k 从第几个人开始
     * @param m 开始后数到m的人踢出，其下一位继续报m个数
     * @description 已知问题 不可以让m等于1 修复手段 见Que2！
     * @author 俊昭
     * @date 2022/4/28
     */
    public static void pop(int k, int m) {
        Node temp = head;

        // 找到第k个人
        for (int i = 0; i < k; ) {
            if (temp.next != tail && temp != tail) {// 画个图就明白咯！
                i++;
            }
            temp = temp.next;
        }

        // 报m-1下踢出 直到没有为止 稍微有点复杂但是画出来也好理解
        while (head.next != tail) {
            for (int i = 1; i < m; ) {
                if (temp.next != tail && temp != tail) {// 画个图就明白咯！

                    if (i == m - 1) {
                        System.out.println(temp.next);
                        temp.next = temp.next.next;// 不可达被回收
                    }
                    i++;
                }
                temp = temp.next;
            }
        }
    }
}

class JosephuQueTest {
    public static void main(String[] args) {
        JosephuQue.addNode(5);
        JosephuQue.pop(6, 2);
        System.out.println();
        JosephuQue.addNode(5);
        JosephuQue.pop(1, 2);
    }
}

